package hzk.codex2016.list;

public class LinkedList_hasCycle {

	/**
	 * https://leetcode.com/problems/linked-list-cycle/
	 * 
	 * @param head
	 * @return
	 */
	public boolean hasCycle(ListNode head) {
		if (head == null || head.next == null)
			return false;
		ListNode slow = head, fast = head.next;

		while (fast != null && fast.next != null) {
			if (slow == fast)
				return true;
			slow = slow.next;
			fast = fast.next.next;
		}
		return false;
	}

	/**
	 * https://leetcode.com/problems/linked-list-cycle-ii/
	 * 
	 * @param head
	 * @return
	 */
	public ListNode detectCycle(ListNode head) {
		if (head == null || head.next == null || head.next.next==null)
			return null;
		ListNode p, slow = head.next, fast = head.next.next;
		while (fast != null && fast.next != null && slow != fast) {
			slow = slow.next;
			fast = fast.next.next;
		}
		if (slow!=fast){
			return null;
		}
		ListNode meet=slow;
		slow=head;
		fast=meet;
		while (slow!=fast){
			slow=slow.next;
			fast=fast.next;
		}
		return slow;
		
	}

	public static void main(String[] args) {
		LinkedList_hasCycle s = new LinkedList_hasCycle();

		ListNode a = new ListNode(1);
		ListNode b = new ListNode(2);
		ListNode c = new ListNode(3);
		ListNode d = new ListNode(4);
		a.next = b;
		b.next = c;
		c.next = d;
		d.next = b;
		ListNode e = new ListNode(14);
		ListNode f = new ListNode(15);
		e.next=f;f.next=e;
		System.out.println(s.hasCycle(a));
		System.out.println(s.detectCycle(a));
		System.out.println(s.detectCycle(e));
	}
}
